import java.util.Stack;

public class Sort {
    public void swap(int[] array, int i, int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    /**
     * 插入排序
     * 时间复杂度   O(N^2)
     * 稳定
     * @param array
     */
    public void insertSort(int[] array){
        for(int i = 1; i < array.length; i++){
            int tmp = array[i];
            int j = i-1;
            for(; j >= 0; j--){
                if(array[j] > tmp){
                    array[j+1] = array[j];
                }
                else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

    /**
     * 希尔排序
     * 时间复杂度   O(logN * N)
     * 不稳定
     * @param array
     */
    public void shellSort(int[] array){
        int gap = array.length;
        while(gap > 1){
            gap /= 2;
            shell(array, gap);
        }
    }
    public void shell(int[] array, int gap){
        for(int i = gap; i < array.length; i++){
            int tmp = array[i];
            int j = i-gap;
            for(; j >= 0; j -= gap){
                if(array[j] > tmp){
                    array[j+gap] = array[j];
                }
                else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }

    /**
     * 选择排序
     * 时间复杂度   O(N^2)
     * 不稳定
     * @param array
     */
    public void selectSort(int[] array){
        int head = 0;
        int end = array.length-1;
        while(head < end){
            int minIndex = head;
            int maxIndex = end;
            for(int i = head; i < end; i++){
                if(array[i] < array[minIndex])
                    minIndex = i;
                if(array[i] > array[maxIndex])
                    maxIndex = i;
            }
            swap(array, minIndex, head);
            if(maxIndex == head)
                maxIndex = minIndex;
            swap(array, maxIndex, end);
            head++;
            end--;
        }
    }

    /**
     * 冒泡排序
     * 时间复杂度   O(N^2)
     * 稳定
     * @param array
     */
    public void bubbleSort(int[] array){
        for(int i = 0; i < array.length-1; i++){
            boolean flag = false;
            for(int j = 0; j < array.length-1-i; j++){
                if (array[j] > array[j+1]){
                    swap(array, j, j+1);
                    flag = true;
                }
            }
            if(!flag)
                break;
        }
    }


    /**
     * 堆排序
     * 时间复杂度   O(N^log2 N)
     * 空间复杂度   O(1)
     * 不稳定
     * @param array
     */
    public void siftDown(int[]array, int parent, int end){
        int child = parent*2 + 1;
        while(child < end){
            if(child+1 < end && array[child] < array[child+1]){
                child++;
            }
            if(array[parent] < array[child]){
                swap(array, parent, child);
                parent = child;
                child = parent*2 - 1;
            }else{
                break;
            }
        }
    }
    public void createdHeap(int[] array){
        for(int parent = (array.length-2)/2; parent >= 0; parent--){
            siftDown(array, parent, array.length);
        }
    }
    public void heapSort(int[] array){
        createdHeap(array);
        int endIndex = array.length-1;
        while(endIndex > 0){
            swap(array, endIndex, 0);
            siftDown(array, 0, endIndex);
            endIndex--;
        }
    }

    /**
     * 快速排序
     * 时间复杂度   O(N^log2 N)
     * 空间复杂度   O(N)
     * 不稳定
     * @param array
     */

    // Hoare版  因递归次数太多会栈溢出
    public int partitionHoare(int[] array, int left, int right){
        int tmp = left;
        while(left < right){
            while(left < right && array[right] >= array[tmp])
                right--;
            while(left < right && array[left] <= array[tmp])
                left++;
            swap(array, left, right);
        }
        swap(array, tmp, left);
        return left;
    }
    public void quickSortHoare(int[] array, int start, int end){
        if(start >= end)
            return ;
        int par = partitionHoare(array, start, end);
        quickSortHoare(array, start, par-1);
        quickSortHoare(array, par+1, end);
    }
    //挖坑版
    public int partitionPit(int[] array, int left, int right){
        int tmp = array[left];
        while(left < right){
            while(left < right && array[right] >= tmp)
                right--;
            array[left] = array[right];
            while(left < right && array[left] <= tmp)
                left++;
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }
    public void quickSortPit(int[] array, int start, int end){
        if(start >= end)
            return ;
        int par = partitionPit(array, start, end);
        quickSortPit(array, start, par-1);
        quickSortPit(array, par+1, end);
    }
    //前后指针版
    public int partitionPointer(int[] array, int left, int right){
        int prev = left;
        int cur = left+1;
        while(cur <= right){
            if(array[cur] < array[left] && array[++prev] != array[cur])
                swap(array, prev, cur);
            cur++;
        }
        swap(array, prev, left);
        return prev;
    }
    public void quickSortPointer(int[] array, int start, int end){
        if(start >= end)
            return ;
        int par = partitionPointer(array, start, end);
        quickSortPointer(array, start, par-1);
        quickSortPointer(array, par+1, end);
    }

    /*
     快速排序优化
     */
    //三数取中法
    public int midTreeNum(int[] array, int left, int right){
        int mid = (left+right) / 2;
        if(array[left] < array[right]){
            if(array[mid] < array[left])
                return left;
            else if(array[mid] > array[right])
                return right;
            else
                return mid;
        }
        else{
            if(array[mid] < array[right])
                return right;
            else if(array[mid] > array[left])
                return left;
            return mid;
        }
    }
    public void quickSortHoareOptimize(int[] array, int start, int end){
        if(start >= end)
            return ;
        int index = midTreeNum(array, start, end);
        swap(array, start, index);
        int par = partitionHoare(array, start, end);
        quickSortHoareOptimize(array, start, par-1);
        quickSortHoareOptimize(array, par+1, end);
    }
    //递归到小区间使用插入排序
    public void insertSortRange(int[] array, int left, int end){
        for(int i = left+1; i <= end; i++){
            int tmp = array[i];
            int j = i-1;
            for(; j >= left; j--){
                if(array[j] > tmp){
                    array[j+1] = array[j];
                }
                else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    public void quickSortHoareInsert(int[] array, int start, int end){
        if(start >= end)
            return ;
        if(end-start < 10) {
            insertSortRange(array, start, end);
            return ;
        }
        int par = partitionHoare(array, start, end);
        quickSortHoareOptimize(array, start, par-1);
        quickSortHoareOptimize(array, par+1, end);
    }

    /*
    不使用递归实现快速排序
     */
    public void quickSortNotRecursion(int[] array){
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length-1;
        if(right <= left)
            return ;
        stack.push(left);
        stack.push(right);
        while(!stack.isEmpty()){
            right = stack.pop();
            left = stack.pop();
            int par = partitionPit(array, left, right);
            if(par > left+1){
                stack.push(left);
                stack.push(par-1);
            }
            if(par < right-1){
                stack.push(par+1);
                stack.push(right);
            }
        }
    }

    public void quickSort(int[] array){
        quickSortNotRecursion(array);
    }

    /**
     * 归并排序
     * 时间复杂度   O(N*log2 N)
     * 空间复杂度   O(N)
     * 稳定性   稳定
     * @param array
     */
    public void mergeSort(int[] array){
        mergeSortFunc(array, 0, array.length-1);
    }
    public void mergeSortFunc(int[] array, int left, int right){
        if(left >= right)
            return ;
        int mid = (left + right) / 2;
        mergeSortFunc(array, left, mid);
        mergeSortFunc(array, mid+1, right);
        merge(array, left, mid, right);
    }
    public void merge(int[] array, int left, int mid, int right){
        int[] tmp = new int[right-left+1];
        int k = 0;
        int left1 = left;
        int left2 = mid+1;
        while(left1 <= mid && left2 <= right){
            if(array[left1] > array[left2]){
                tmp[k++] = array[left2++];
            }
            else{
                tmp[k++] = array[left1++];
            }
        }
        while(left1 <= mid){
            tmp[k++] = array[left1++];
        }
        while(left2 <= right){
            tmp[k++] = array[left2++];
        }
        for(int i = 0; i < k; i++){
            array[i+left] = tmp[i];
        }
    }


}